<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.8.0">
  <meta charset="utf-8">
  

  
  <title>线段树 | Hexo</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="线段树引例区间最值给定一个n（n &amp;lt;= 100000）个元素的数组A，有m(m &amp;lt;= 100000)个操作，共两种操作：    1、Q a b         询问：表示询问区间[a, b]的最大值；    2、C a c         更新：表示将第a个元素变成c；静态的区间最值可以利用RMQ来解决，但是RMQ的ST算法是在元素值给定的情况下进行的预处理，然后在O(1)时间内进行询">
<meta property="og:type" content="article">
<meta property="og:title" content="线段树">
<meta property="og:url" content="http://yoursite.com/2018/12/08/线段树/index.html">
<meta property="og:site_name" content="Hexo">
<meta property="og:description" content="线段树引例区间最值给定一个n（n &amp;lt;= 100000）个元素的数组A，有m(m &amp;lt;= 100000)个操作，共两种操作：    1、Q a b         询问：表示询问区间[a, b]的最大值；    2、C a c         更新：表示将第a个元素变成c；静态的区间最值可以利用RMQ来解决，但是RMQ的ST算法是在元素值给定的情况下进行的预处理，然后在O(1)时间内进行询">
<meta property="og:locale" content="default">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207110846027_1448.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207111114500_27601.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207111637834_25314.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207113729226_21546.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207113902281_4828.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207114638650_28249.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207114740882_26524.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207114821265_8530.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207114911688_27038.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207115318764_16033.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207115741584_19283.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207120153733_2563.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207124228603_27615.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207124326654_7829.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207124434815_25668.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207124538116_1457.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207124803902_26159.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207125042295_25049.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207125435128_5407.webp%20=676x">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207125557701_20335.webp">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207130453688_3915.webp%20=658x">
<meta property="og:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207131222478_448.webp">
<meta property="og:updated_time" content="2018-12-08T03:08:50.056Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="线段树">
<meta name="twitter:description" content="线段树引例区间最值给定一个n（n &amp;lt;= 100000）个元素的数组A，有m(m &amp;lt;= 100000)个操作，共两种操作：    1、Q a b         询问：表示询问区间[a, b]的最大值；    2、C a c         更新：表示将第a个元素变成c；静态的区间最值可以利用RMQ来解决，但是RMQ的ST算法是在元素值给定的情况下进行的预处理，然后在O(1)时间内进行询">
<meta name="twitter:image" content="http://yoursite.com/2018/12/08/线段树/_v_images/20181207110846027_1448.webp">
  
    <link rel="alternate" href="/atom.xml" title="Hexo" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  <link rel="stylesheet" href="/css/style.css">
</head>
</html>
<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">Hexo</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="Search"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://yoursite.com"></form>
      </div>
    </div>
  </div>
</header>
      <div class="outer">
        <section id="main"><article id="post-线段树" class="article article-type-post" itemscope="" itemprop="blogPost">
  <div class="article-meta">
    <a href="/2018/12/08/线段树/" class="article-date">
  <time datetime="2018-12-08T03:05:12.000Z" itemprop="datePublished">2018-12-08</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      线段树
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h1 id="线段树"><a href="#线段树" class="headerlink" title="线段树"></a>线段树</h1><h2 id="引例"><a href="#引例" class="headerlink" title="引例"></a>引例</h2><h3 id="区间最值"><a href="#区间最值" class="headerlink" title="区间最值"></a>区间最值</h3><p>给定一个n（n &lt;= 100000）个元素的数组A，有m(m &lt;= 100000)个操作，共两种操作：<br>    1、Q a b         询问：表示询问区间[a, b]的最大值；<br>    2、C a c         更新：表示将第a个元素变成c；<br>静态的区间最值可以利用RMQ来解决，但是RMQ的ST算法是在元素值给定的情况下进行的预处理，然后在O(1)时间内进行询问，这里第二种操作需要实时修改某个元素的值，所以无法进行预处理。<br>由于每次操作都是独立事件，所以m次操作都无法互相影响，于是时间复杂度的改善只能在单次操作上进行优化了，我们可以试想能否将任何的区间[a, b]（a &lt; b）都拆成log(b-a+1)个小区间，然后只对这些拆散的区间进行询问，这样每次操作的最坏时间复杂度就变成log(n)了。</p>
<h3 id="区间求和"><a href="#区间求和" class="headerlink" title="区间求和"></a>区间求和</h3><p>给定一个n(n &lt;= 100000)个元素的数组A，有m(m &lt;= 100000)个操作，共两种操作：<br>    1、Q a b         询问：表示询问区间[a, b]的元素和；<br>    2、A a b c       更新：表示将区间[a, b]的每个元素加上一个值c；<br>先来看朴素算法，两个操作都用遍历来完成，单次时间复杂度在最坏情况下都是O(n)的，所以m次操作下来总的时间复杂度就是O(nm)了，复杂度太高。<br>再来看看树状数组，对于第一类操作，树状数组可以在log(n)的时间内出解；然而第二类操作，还是需要遍历每个元素执行add操作，复杂度为nlog(n)，所以也不可行。这个问题同样也需要利用区间拆分的思想。<br>线段树就是利用了区间拆分的思想，完美解决了上述问题。</p>
<h2 id="基本概念"><a href="#基本概念" class="headerlink" title="基本概念"></a>基本概念</h2><h3 id="二叉搜索树"><a href="#二叉搜索树" class="headerlink" title="二叉搜索树"></a>二叉搜索树</h3><p>线段树是一种二叉搜索树，即每个结点最多有两棵子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。线段树的每个结点存储了一个区间（线段），故而得名。<br><img src="_v_images/20181207110846027_1448.webp" alt="二叉搜索树"><br>如图所示，表示的是一个[1, 6]的区间的线段树结构，每个结点存储一个区间（注意这里的存储区间并不是指存储这个区间里面所有的元素，而是只需要存储区间的左右端点即可），所有叶子结点表示的是单位区间（即左右端点相等的区间），所有非叶子结点（内部结点）都有左右两棵子树，对于所有非叶子结点，它表示的区间为[l, r]，那么令mid为(l + r)/2的下整，则它的左儿子表示的区间为[l, mid]，右儿子表示的区间为[mid+1, r]。基于这个特性，这种二叉树的内部结点，一定有两个儿子结点，不会存在有左儿子但是没有右儿子的情况。<br>基于这种结构，叶子结点保存一个对应原始数组下标的值，由于树是一个递归结构，两个子结点的区间并正好是父结点的区间，可以通过自底向上的计算在每个结点都计算出当前区间的最大值。<br>需要注意的是，基于线段树的二分性质，所以它是一棵平衡树，树的高度为log(n)。</p>
<h3 id="数据域"><a href="#数据域" class="headerlink" title="数据域"></a>数据域</h3><p>了解线段树的基本结构以后，看看每个结点的数据域，即需要存储哪些信息。<br>首先，既然线段树的每个结点表示的是一个区间，那么必须知道这个结点管辖的是哪个区间，所以其中最重要的数据域就是区间左右端点[l, r]。然而有时候为了节省全局空间，往往不会将区间端点存储在结点中，而是通过递归的传参进行传递，实时获取。<br>再者，以区间最大值为例，每个结点除了需要知道所管辖的区间范围[l, r]以外，还需要存储一个当前区间内的最大值max。<br><img src="_v_images/20181207111114500_27601.webp" alt="线段树数据域"><br>以数组A[1:6] = [1 7 2 5 6 3]为例，建立如图的线段树，叶子结点的max域为数组对应下标的元素值，非叶子结点的max域则通过自底向上的计算由两个儿子结点的max域比较得出。这是一棵初始的线段树，接下来讨论下线段树的询问和更新操作。<br>在询问某个区间的最大值时，我们一定可以将这个区间拆分成log(n)个子区间，并且这些子区间一定都能在线段树的结点上找到（这一点下文会着重讲解），然后只要比较这些结点的max域，就能得出原区间的最大值了，因为子区间数量为log(n)，所以时间复杂度是O( log(n) )。<br>更新数组某个元素的值时我们首先修改对应的叶子结点的max域，然后修改它的父结点的max域，以及祖先结点的max域，换言之，修改的只是线段树的叶子结点到根结点的某一条路径上的max域，又因为树高是log(n)，所以这一步操作的时间复杂度也是log(n)的。</p>
<h3 id="指针表示"><a href="#指针表示" class="headerlink" title="指针表示"></a>指针表示</h3><p>接下来讨论一下结点的表示法，每个结点可以看成是一个结构体指针，由数据域和指针域组成，其中指针域有两个，分别为左儿子指针和右儿子指针，分别指向左右子树；数据域存储对应数据，根据情况而定(如果是求区间最值，就存最值max；求区间和就存和sum)，这样就可以利用指针从根结点进行深度优先遍历了。<br>以下是简单的线段树结点的C++结构体：    </p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">treeNode</span> &#123;</span></span><br><span class="line">        Data data;                 <span class="comment">// 数据域</span></span><br><span class="line">        treeNode *lson, *rson;     <span class="comment">// 指针域</span></span><br><span class="line">    &#125;*root;</span><br></pre></td></tr></table></figure>
<h3 id="数组表示"><a href="#数组表示" class="headerlink" title="数组表示"></a>数组表示</h3><p>实际计算过程中，还有一种更加方便的表示方法，就是基于数组的静态表示法，需要一个全局的结构体数组，每个结点对应数组中的一个元素，利用下标索引。<br>例如，假设某个结点在数组中下标为p，那么它的左儿子结点的下标就是2<em>p，右儿子结点的下标就是2</em>p+1(类似于一般数据结构书上说的堆在数组中的编号方式)，这样可以将所有的线段树结点存储在相对连续的空间内。之所以说是相对连续的空间，是因为有些下标可能永远用不到。<br>还是以长度为6的数组为例，如下图所示，红色数字表示结点对应的数组下标，由于树的结构和编号方式，导致数组的第10、11位置空缺。<br><img src="_v_images/20181207111637834_25314.webp" alt="线段树数组表示"><br>这种存储方式可以不用存子结点指针，取而代之的是当前结点的数组下标索引。<br>以下是数组存储方式的线段树结点的C++结构体： </p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">treeNode</span> &#123;</span>        </span><br><span class="line">    Data data;                         <span class="comment">// 数据域</span></span><br><span class="line">    <span class="keyword">int</span> pid;                           <span class="comment">// 数组下标索引</span></span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">lson</span><span class="params">()</span> </span>&#123; <span class="keyword">return</span> pid &lt;&lt; <span class="number">1</span>; &#125;        </span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">rson</span><span class="params">()</span> </span>&#123; <span class="keyword">return</span> pid&lt;&lt;<span class="number">1</span>|<span class="number">1</span>; &#125;    <span class="comment">// 利用位运算加速获取子结点编号</span></span><br><span class="line">&#125;nodes[MAXNODES];</span><br></pre></td></tr></table></figure>
<p>接下来我们关心的就是MAXNODES的取值了，由于线段树是一种二叉树，所以当区间长度为2的幂时，它正好是一棵满二叉树，数组存储的利用率达到最高（即100%），根据等比数列求和可以得出，满二叉树的结点个数为2n-1，其中n为区间长度（由于C++中数组长度从0计数，编号从1开始，所以MAXNODES要取2n）。那么是否对于所有的区间长度n都满足这个公式呢？答案是否定的，当区间长度为6时，最大的结点编号为13，而公式算出来的是12（2 <em> 6）。<br>那么 MAXNODES 取多少合适呢？<br>为了保险起见，我们可以先找到比n大的最小的二次幂，然后再套用等比数列求和公式，这样就万无一失了。举个例子，当区间长度为6时，MAXNODES = 2 </em> 8；当区间长度为1000，则MAXNODES = 2 <em> 1024；当区间长度为10000，MAXNODES = 2 </em>16384。至于为什么可以这样，明眼人一看便知。<br><strong>一般取4n即可。</strong></p>
<h2 id="线段树的基本操作"><a href="#线段树的基本操作" class="headerlink" title="线段树的基本操作"></a>线段树的基本操作</h2><p>线段树的基本操作包括构造、更新、询问，都是深度优先搜索的过程。</p>
<h3 id="构造"><a href="#构造" class="headerlink" title="构造"></a>构造</h3><p>线段树的构造是一个二分递归的过程，封装好了之后代码非常简洁，总体思路就是从区间[1, n]开始拆分，拆分方式为二分的形式，将左半区间分配给左子树，右半区间分配给右子树，继续递归构造左右子树。<br>当区间拆分到单位区间时（即遍历到了线段树的叶子结点），则执行回溯。回溯时对于任何一个非叶子结点需要根据两棵子树的情况进行统计，计算当前结点的数据域，详见注释4。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">segtree_build</span><span class="params">(<span class="keyword">int</span> p, <span class="keyword">int</span> l, <span class="keyword">int</span> r)</span> </span>&#123;</span><br><span class="line">        nodes[p].reset(p, l, r);                  <span class="comment">// 注释1</span></span><br><span class="line">        <span class="keyword">if</span> (l &lt; r) &#123;</span><br><span class="line">            <span class="keyword">int</span> mid = (l + r) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">            segtree_build(p&lt;&lt;<span class="number">1</span>, l, mid);          <span class="comment">// 注释2</span></span><br><span class="line">            segtree_build(p&lt;&lt;<span class="number">1</span>|<span class="number">1</span>, mid+<span class="number">1</span>, r);      <span class="comment">// 注释3</span></span><br><span class="line">            nodes[p].updateFromSon();             <span class="comment">// 注释4</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>
<p>注释1：初始化第p个结点的数据域，根据实际情况实现reset函数<br>注释2：递归构造左子树<br>注释3：递归构造右子树<br>注释4：回溯，利用左右子树的信息来更新当前结点，updateFromSon这个函数的实现需要根据实际情况进行求解，在第四节会详细讨论<br>构造线段树的调用如下：build(1, 1, n);</p>
<h3 id="更新"><a href="#更新" class="headerlink" title="更新"></a>更新</h3><p>线段树的更新是指更新数组在[x, y]区间的值，具体更新这件事情是做了什么要根据具体情况而定，可以是将[x, y]区间的值都变成val（覆盖），也可以是将[x, y]区间的值都加上val（累加）。<br>更新过程采用二分，将[1, n]区间不断拆分成一个个子区间[l, r]，当更新区间[x, y]完全覆盖被拆分的区间[l, r]时，则更新管辖[l, r]区间的结点的数据域，详见注释2和注释3。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">segtree_insert</span><span class="params">(<span class="keyword">int</span> p, <span class="keyword">int</span> l, <span class="keyword">int</span> r, <span class="keyword">int</span> x, <span class="keyword">int</span> y, ValueType val)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>( !is_intersect(l, r, x, y) ) &#123;              <span class="comment">// 注释1</span></span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    &#125; </span><br><span class="line">    <span class="keyword">if</span>( is_contain(l, r, x, y) ) &#123;                 <span class="comment">// 注释2</span></span><br><span class="line">        nodes[p].updateByValue(val);               <span class="comment">// 注释3</span></span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    &#125; </span><br><span class="line">    nodes[p].giveLazyToSon();                      <span class="comment">// 注释4</span></span><br><span class="line">                <span class="keyword">int</span> mid = (l + r) &gt;&gt; <span class="number">1</span>; </span><br><span class="line">    segtree_insert(p&lt;&lt;<span class="number">1</span>, l, mid, x, y, val);       <span class="comment">// 注释5</span></span><br><span class="line">    segtree_insert(p&lt;&lt;<span class="number">1</span>|<span class="number">1</span>, mid+<span class="number">1</span>, r, x, y, val);   <span class="comment">// 注释6</span></span><br><span class="line">    nodes[p].updateFromSon();                      <span class="comment">// 注释7</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>注释1：区间[l, r]和区间[x, y]无交集，直接返回<br>注释2：区间[x, y]完全覆盖[l, r]<br>注释3：更新第p个结点的数据域，updateByValue这个函数的实现需要根据具体情况而定，会在第四节进行详细讨论<br>注释4：参见第五节的lazy-tag<br>注释5：递归更新左子树<br>注释6：递归更新右子树<br>注释7：回溯，利用左右子树的信息来更新当前结点<br>更新区间[x, y]的值为val的调用如下：segtree_insert(1, 1, n, x, y, val);</p>
<h3 id="询问"><a href="#询问" class="headerlink" title="询问"></a>询问</h3><p>线段树的询问和更新类似，大部分代码都是一样的，同样是将大区间[1, n]拆分成一个个小区间[l, r]，这里需要存储一个询问得到的结果ans，当询问区间[x, y]完全覆盖被拆分的区间[l, r]时，则用管辖[l, r]区间的结点的数据域来更新ans，详见注释1的mergeQuery接口 。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">segtree_query</span> <span class="params">(<span class="keyword">int</span> p, <span class="keyword">int</span> l, <span class="keyword">int</span> r, <span class="keyword">int</span> x, <span class="keyword">int</span> y, treeNode&amp; ans)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>( !is_intersect(l, r, x, y) ) &#123;</span><br><span class="line">              <span class="keyword">return</span> ;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>( is_contain(l, r, x, y) ) &#123;</span><br><span class="line">        ans.mergeQuery(p);                          <span class="comment">// 注释1</span></span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    nodes[p].giveLazyToSon();</span><br><span class="line">                <span class="keyword">int</span> mid = (l + r) &gt;&gt; <span class="number">1</span>; </span><br><span class="line">    segtree_query(p&lt;&lt;<span class="number">1</span>, l, mid, x, y, ans);</span><br><span class="line">    segtree_query(p&lt;&lt;<span class="number">1</span>|<span class="number">1</span>, mid+<span class="number">1</span>, r, x, y, ans);</span><br><span class="line">    nodes[p].updateFromSon();                       <span class="comment">// 注释2</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>注释1：更新当前解ans，会在第四节进行详细讨论<br>注释2：和更新一样的代码，不再累述</p>
<h2 id="线段树的经典案例"><a href="#线段树的经典案例" class="headerlink" title="线段树的经典案例"></a>线段树的经典案例</h2><p>线段树的用法千奇百怪，接下来介绍几个线段树的经典案例，加深对线段树的理解。</p>
<h3 id="区间最值-1"><a href="#区间最值-1" class="headerlink" title="区间最值"></a>区间最值</h3><p>区间最值是最常见的线段树问题，引例中已经提到。接下来从几个方面来讨论下区间最值是如何运作的。</p>
<h4 id="数据域："><a href="#数据域：" class="headerlink" title="数据域："></a>数据域：</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> pid;               <span class="comment">// 数组索引</span></span><br><span class="line"><span class="keyword">int</span> l, r;              <span class="comment">// 结点区间(一般不需要存储)       </span></span><br><span class="line">ValyeType max;         <span class="comment">// 区间最大值</span></span><br></pre></td></tr></table></figure>
<h4 id="初始化："><a href="#初始化：" class="headerlink" title="初始化："></a>初始化：</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">void</span> treeNode::reset(<span class="keyword">int</span> p, <span class="keyword">int</span> l, <span class="keyword">int</span> r) &#123;</span><br><span class="line">    pid = p;</span><br><span class="line">    max = srcArray[l]; <span class="comment">// 初始化只对叶子结点有效</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="单点更新："><a href="#单点更新：" class="headerlink" title="单点更新："></a>单点更新：</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">void</span> treeNode::updateByValue(ValyeType val) &#123;</span><br><span class="line">    max = val;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="合并结点："><a href="#合并结点：" class="headerlink" title="合并结点："></a>合并结点：</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">void</span> treeNode::mergeQuery(<span class="keyword">int</span> p) &#123;</span><br><span class="line">    max = getmax( max, nodes[p].max );</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="回溯统计："><a href="#回溯统计：" class="headerlink" title="回溯统计："></a>回溯统计：</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">void</span> treeNode::updateFromSon() &#123;</span><br><span class="line">    max = nodes[ lson() ].max;</span><br><span class="line">    mergeQuery( rson() );</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>结合上一节线段树的基本操作，在构造线段树的时候，对每个结点执行了一次初始化，初始化同时也是单点更新的过程，然后在回溯的时候统计，统计实质上是合并左右结点的过程，合并结点做的事情就是更新最大值；询问就是将给定区间拆成一个个能够在线段树结点上找到的区间，然后合并这些结点的过程，合并的结果ans一般通过引用进行传参，或者作为全局变量，不过尽量避免使用全局变量。</p>
<h3 id="区间求和-1"><a href="#区间求和-1" class="headerlink" title="区间求和"></a>区间求和</h3><p>区间求和问题一般比区间最值稍稍复杂一点，因为涉及到区间更新和区间询问，如果更新和询问都只遍历到询问（更新）区间完全覆盖结点区间的话，会导致计算遗留，举个例子来说明。<br>用一个数据域sum来记录线段树结点区间上所有元素的和，初始化所有结点的sum值都为0，然后在区间[1, 4]上给每个元素加上4，如下图所示：<br><img src="_v_images/20181207113729226_21546.webp" alt="线段树区间求和"><br>图中[1, 4]区间完全覆盖[1, 3]和[4, 4]两个子区间，然后分别将值累加到对应结点的数据域sum上，再通过回溯统计sum和，最后得到[1, 6]区间的sum和为16，看上去貌似天衣无缝，但是实际上操作一多就能看出这样做是有缺陷的。例如当我们要询问[3, 4]区间的元素和时，在线段树结点上得到被完全覆盖的两个子区间[3, 3]和[4, 4]，累加区间和为0 + 4 = 4，如图所示。<br><img src="_v_images/20181207113902281_4828.webp" alt="线段树区间求和2"><br>这是因为在进行区间更新的时候，由于[1, 4]区间完全覆盖[1, 3]区间，所以我们并没有继续往下遍历，而是直接在[1, 3]这个结点进行sum值的计算，计算完直接回溯。等到下一次访问[3, 3]的时候，它并不知道之前在3号位置上其实是有一个累加值4的，但是如果每次更新都更新到叶子结点，就会使得更新的复杂度变成O(n)，违背了使用线段树的初衷，所以这里需要引入一个lazy-tag的概念。<br>所谓lazy-tag，就是在某个结点打上一个“懒惰标记”，每次更新的时候只要更新区间完全覆盖结点区间，就在这个结点打上一个lazy标记，这个标记的值就是更新的值，表示这个区间上每个元素都有一个待累加值lazy，然后计算这个结点的sum，回溯统计sum。<br>    当下次访问到有lazy标记的结点时，如果还需要往下访问它的子结点，则将它的lazy标记传递给两个子结点，自己的lazy标记置空。<br>    这就是为什么在之前在讲线段树的更新和询问的时候有一个函数叫giveLazyToSon了。接下来看看一些函数的实现。</p>
<h4 id="数据域：-1"><a href="#数据域：-1" class="headerlink" title="数据域："></a>数据域：</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> pid;               <span class="comment">// 数组索引</span></span><br><span class="line"><span class="keyword">int</span> len;               <span class="comment">// 结点区间长度</span></span><br><span class="line">ValyeType sum;         <span class="comment">// 区间元素和 </span></span><br><span class="line">ValyeType lazy;        <span class="comment">// lazy tag</span></span><br></pre></td></tr></table></figure>
<h4 id="初始化：-1"><a href="#初始化：-1" class="headerlink" title="初始化："></a>初始化：</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">void</span> treeNode::reset(<span class="keyword">int</span> p, <span class="keyword">int</span> l, <span class="keyword">int</span> r) &#123;</span><br><span class="line">    pid = p;</span><br><span class="line">    len = r - l + <span class="number">1</span>;</span><br><span class="line">    sum = lazy = <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="单点更新：-1"><a href="#单点更新：-1" class="headerlink" title="单点更新："></a>单点更新：</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">void</span> treeNode::updateByValue(ValyeType val) &#123;</span><br><span class="line">    lazy += val;</span><br><span class="line">    sum += val * len;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="lazy标记继承："><a href="#lazy标记继承：" class="headerlink" title="lazy标记继承："></a>lazy标记继承：</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">void</span> treeNode::giveLazyToSon() &#123;</span><br><span class="line">    <span class="keyword">if</span>( lazy ) &#123;</span><br><span class="line">       nodes[ lson() ].updateByValue(lazy);</span><br><span class="line">       nodes[ rson() ].updateByValue(lazy);</span><br><span class="line">       lazy = <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="合并结点：-1"><a href="#合并结点：-1" class="headerlink" title="合并结点："></a>合并结点：</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">void</span> treeNode::mergeQuery(<span class="keyword">int</span> p) &#123;</span><br><span class="line">    sum += nodes[p].sum;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="回溯统计：-1"><a href="#回溯统计：-1" class="headerlink" title="回溯统计："></a>回溯统计：</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">void</span> treeNode::updateFromSon() &#123;</span><br><span class="line">    sum = nodes[ lson() ].sum;</span><br><span class="line">    mergeQuery( rson() );</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>对比区间最值，区间求和的几个函数的实现主旨是一致的，因为引入了lazy-tag，所以需要多实现一个函数用于lazy标记的继承，在进行区间求和的时候还需要记录一个区间的长度len，用于更新的时候计算累加的sum值。</p>
<h3 id="区间染色"><a href="#区间染色" class="headerlink" title="区间染色"></a>区间染色</h3><p>给定一个长度为n(n &lt;= 100000)的木板，支持两种操作：<br>    1、P a b c       将[a, b]区间段染色成c；<br>    2、Q a b         询问[a, b]区间内有多少种颜色；<br>保证染色的颜色数少于30种。<br>对比区间求和，不同点在于区间求和的更新是对区间和进行累加；而这类染色问题则是对区间的值进行替换（或者叫覆盖），有一个比较特殊的条件是颜色数目小于30。<br>我们是不是要将30种颜色的有无与否都存在线段树的结点上呢？答案是肯定的，但是这样一来每个结点都要存储30个bool值，空间太浪费，而且在计算合并操作的时候有一步30个元素的遍历，大大降低效率。然而30个bool值正好可以压缩在一个int32中，利用二进制压缩可以用一个32位的整型完美的存储30种颜色的有无情况。<br>因为任何一个整数都可以分解成二进制整数，二进制整数的每一位要么是0，要么是1。二进制整数的第i位是1表示存在第i种颜色；反之不存在。<br>数据域需要存一个颜色种类的位或和colorBit，一个颜色的lazy标记表示这个结点被完全染成了lazy，基本操作的几个函数和区间求和非常像，这里就不出示代码了。<br>和区间求和不同的是回溯统计的时候，对于两个子结点的数据域不再是加和，而是位或和。</p>
<h3 id="矩形面积并"><a href="#矩形面积并" class="headerlink" title="矩形面积并"></a>矩形面积并</h3><p>给定n(n &lt;= 100000)个平行于XY轴的矩形，求它们的面积并。如图所示。<br><img src="_v_images/20181207114638650_28249.webp" alt="矩形面积并"><br>这类二维的问题同样也可以用线段树求解，核心思想是降维，将某一维套用线段树，另外一维则用来枚举。具体过程如下：</p>
<h4 id="第一步："><a href="#第一步：" class="headerlink" title="第一步："></a>第一步：</h4><p>将所有矩形拆成两条垂直于x轴的线段，平行x轴的边可以舍去，如图所示。<br><img src="_v_images/20181207114740882_26524.webp" alt="矩形面积并2"></p>
<h4 id="第二步："><a href="#第二步：" class="headerlink" title="第二步："></a>第二步：</h4><p>定义矩形的两条垂直于x轴的边中x坐标较小的为入边，x坐标较大的为出边，入边权值为+1，出边权值为-1，并将所有的线段按照x坐标递增排序，第i条线段的x坐标记为X[i]，如图所示。<br><img src="_v_images/20181207114821265_8530.webp" alt="矩形面积并3"></p>
<h4 id="第三步："><a href="#第三步：" class="headerlink" title="第三步："></a>第三步：</h4><p>将所有矩形端点的y坐标进行重映射(也可以叫离散化)，原因是坐标有可能很大而且不一定是整数，将原坐标映射成小范围的整数可以作为数组下标，更方便计算，映射可以将所有y坐标进行排序去重，然后二分查找确定映射后的值，离散化的具体步骤下文会详细讲解。如图四-4-4所示，蓝色数字表示的是离散后的坐标，即1、2、3、4分别对应原先的5、10、23、25（需支持正查和反查）。假设离散后的y方向的坐标个数为m，则y方向被分割成m-1个独立单元，下文称这些独立单元为“单位线段”，分别记为【1- 2】、【2-3】、【3-4】。<br><img src="_v_images/20181207114911688_27038.webp" alt="矩形面积并4"></p>
<h4 id="第四步："><a href="#第四步：" class="headerlink" title="第四步："></a>第四步：</h4><p>以x坐标递增的方式枚举每条垂直线段，y方向用一个长度为m-1的数组来维护“单位线段”的权值，如下图所示，展示了每条线段按x递增方式插入之后每个“单位线段”的权值。<br><img src="_v_images/20181207115318764_16033.webp" alt="矩形面积并5"><br>当枚举到第i条线段时，检查所有“单位线段”的权值，所有权值大于零的“单位线段”的实际长度之和(离散化前的长度)被称为“合法长度”，记为L，那么(X[i] - X[i-1]) * L，就是第i条线段和第i-1条线段之间的矩形面积和，计算完第i条垂直线段后将它插入，所谓”插入”就是利用该线段的权值更新该线段对应的“单位线段”的权值和（这里的更新就是累加）。<br><img src="_v_images/20181207115741584_19283.webp" alt="矩形面积并6"><br>如图所示：红色、黄色、蓝色三个矩形分别是3对相邻线段间的矩形面积和，其中红色部分的y方向由【1-2】、【2-3】两个“单位线段”组成，黄色部分的y方向由【1-2】、【2-3】、【3-4】三个“单位线段”组成，蓝色部分的y方向由【2-3】、【3-4】两个“单位线段”组成。特殊的，在计算蓝色部分的时候，【1-2】部分的权值由于第3条线段的插入(第3条线段权值为-1)而变为零，所以不能计入“合法长度”。<br>以上所有相邻线段之间的面积和就是最后要求的矩形面积并。</p>
<h4 id="几个问题："><a href="#几个问题：" class="headerlink" title="几个问题："></a>几个问题：</h4><p>1、是否任意相邻两条垂直x轴的线段之间组成的封闭图形都是矩形呢？答案是否定的，如下图所示，其中绿色部分为四个矩形的面积并中的某块有效部分，它们同处于两条相邻线段之间，但是中间有空隙，所以它并不是一个完整的矩形。<br><img src="_v_images/20181207120153733_2563.webp" alt="矩形面积并7"><br>2、每次枚举一条垂直线段的时候，需要检查所有“单位线段”的权值，如果用数组维护权值，那么这一步检查操作是O(m)的，所以总的时间复杂度为O(nm)，其中n表示垂直线段的个数，复杂度太大需要优化。<br>优化自然就是用线段树了，之前提到了降维的思想，x方向我们继续采用枚举，而y方向的“单位线段”则可以采用线段树来维护，和一般问题一样，首先讨论数据域。<br>    数据域：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> pid;        <span class="comment">// 数组索引</span></span><br><span class="line"><span class="keyword">int</span> l, r;       <span class="comment">// 结点代表的“单位线段”区间[l, r] (注意，l和r均为离散后的下标)</span></span><br><span class="line"><span class="keyword">int</span> cover;      <span class="comment">// [l, r]区间被完全覆盖的次数 </span></span><br><span class="line"><span class="keyword">int</span> len;        <span class="comment">// 该结点表示的区间内的合法长度</span></span><br></pre></td></tr></table></figure>
<p>注意，这次的线段树和之前的线段树稍微有点区别，就是叶子结点的区间端点不再相等，而是相差1，即l+1 == r。因为一个点对于计算面积来说是没有意义的。<br>算法采用深度优先搜索的后序遍历，记插入线段为[a, b, v]，其中[a, b]为线段的两个端点，是离散化后的坐标；v是+1或-1，代表是入边还是出边，每次插入操作二分枚举区间，当线段树的结点代表的区间被插入区间完全覆盖时，将权值v累加到结点的cover域上。由于是后续遍历，在子树全部遍历完毕后需要进行统计。插入过程修改cover，同时更新len。<br>回溯统计过程对cover域分情况讨论：<br>当cover &gt; 0时，表示该结点代表的区间至少有一条入边没有被出边抵消，换言之，这块区间都应该在“合法长度”之内，则 len = Y[r] - Y[l]（Y[i]代表离散前第i大的点的y坐标）；更加通俗的理解是至少存在一个矩形的入边被扫描到了，而出边还未被扫描到，所以这块面积需要被计算进来。<br>当cover等于0时，如果该区间是一个单位区间（即上文所说的“单位线段”，l+1 == r，也是线段树的叶子结点），则 len = 0；否则，len需要由左子树和右子树的计算结果得出，又因为是后序遍历，所以左右子树的len都已经计算完毕，从而不需要再进行递归求解，直接将左右儿子的len加和就是答案，即len = lson.len + rson.len。<br><img src="_v_images/20181207124228603_27615.webp" alt="矩形面积并8"><br>上图所示为上述例子的初始线段树，其中根结点管辖的区间为[1, 4]，代表”单位线段”的两个端点。对于线段树上任何一棵子树而言，根结点管辖区间为[l, r]，并且mid = (l + r) / 2，那么如果它不是叶子结点，则它的左子树管辖的区间就是[l, mid]，右子树管辖的区间就是[mid, r]。叶子结点管辖区间的左右端点之差为1（和之前的线段树的区间分配方式稍有不同）。<br>这样就可以利用二分，在O(n)的时间内递归构造初始的线段树。</p>
<h4 id="过程："><a href="#过程：" class="headerlink" title="过程："></a>过程：</h4><p><img src="_v_images/20181207124326654_7829.webp" alt="矩形面积并9"><br>上图所示为插入第一条垂直线段[1, 3, 1]（插入区间[1, 3]，权值为1）后的情况，插入过程类似建树过程，二分递归执行插入操作，当插入区间完全覆盖线段树结点区间时，将权值累加到对应结点（图中绿色箭头指向的结点）的cover域上；否则，继续递归左右子树。然后进行自底向上的统计，统计的是len的值。<br>[2, 4]这个结点的cover域为0，所以它的len等于两棵子树的len之和，[1, 4]亦然。<br><img src="_v_images/20181207124434815_25668.webp" alt="矩形面积并10"><br>上图所示为插入第二条垂直线段[2, 4, 1]（插入区间[2, 4]，权值为1）后的情况，只需要修改一个结点（图中绿色箭头指向的结点）的cover域，该结点的两棵子树不需要再进行递归计算，回溯的时候，计算根结点len值时，由于根结点的cover域为0，所以它的len等于左右子树的len之和。<br><img src="_v_images/20181207124538116_1457.webp" alt="矩形面积并11"><br>上图所示为插入第三条垂直线段[1, 3, -1]（插入区间[1, 3]，权值为-1）后的情况，直观的看，现在Y方向只有[2, 4]一条线段了，所以根结点的len就是Y[4] - Y[2] = 15。<br>讲完插入，就要谈谈询问。在每次插入之前，需要询问之前插入的线段中，在y方向的“合法长度”L，根据线段树结点的定义，y方向“合法长度”总和其实就是根结点的len，所以这一步询问操作其实是O(1)的，在插入过程中已经实时计算出来，再加上插入的O(log n)的时间复杂度，已经完美解决了上述复杂度太大的问题了。</p>
<h3 id="区间K大数"><a href="#区间K大数" class="headerlink" title="区间K大数"></a>区间K大数</h3><p>给定n(n &lt;= 100000)个数的数组，然后m(m &lt;= 100000)条询问，询问格式如下：<br>l r k         询问[l, r]的第K大的数的值<br>这是一个经典的面试题，利用了线段树划分区间的思想，线段树的每个结点存的不只是区间端点，而是这个区间内所有的数，并且是按照递增顺序有序排列的，建树过程是一个归并排序的过程，从叶子结点自底向上进行归并，对于一个长度为6的数组[4, 3, 2, 1, 5, 6]，建立线段树如图所示。<br><img src="_v_images/20181207124803902_26159.webp" alt="区间第k大数"><br>从图中可以看出，线段树的任何一个结点存储了对应区间的数，并且进行有序排列，所以根结点存储的一定是一个长度为数组总长的有序数组，叶子结点存储的递增序列为原数组元素。<br>每次询问，我们将给定区间拆分成一个个线段树上的子区间，然后二分枚举答案T，再利用二分查找统计这些子区间中大于等于T的数的个数，从而确定T是否是第K大的。<br>对于区间K大数的问题，还有很多数据结构都能解决，这里仅作简单介绍。</p>
<h2 id="线段树的常用技巧"><a href="#线段树的常用技巧" class="headerlink" title="线段树的常用技巧"></a>线段树的常用技巧</h2><h3 id="离散化"><a href="#离散化" class="headerlink" title="离散化"></a>离散化</h3><p>在讲解矩形面积并的时候曾经提了一下离散化，现在再详细的说明一下，所谓离散化就是将无限的个体映射到有限的个体中，从而提高算法效率。<br>举个简单的例子，一个实数数组，我想很快的得到某个数在整个数组里是第几大的，并且询问数很多，不允许每次都遍历数组进行比较。<br>    那么，最直观的想法就是对原数组先进行一个排序，询问的时候只需要通过二分查找就能在O( log(n) )的时间内得出这个数是第几大的了，离散化就是做了这一步映射。<br>对于一个数组[1.6, 7.8, 5.5, 11.1111, 99999, 5.5]，离散化就是将原来的实数映射成整数(下标)，如图所示：<br><img src="_v_images/20181207125042295_25049.webp" alt="线段树技巧离散化"><br>这样就可以将原来的实数保存在一个有序数组中，询问第K大的是什么称为正查，可以利用下标索引在O(1)的时间内得到答案；询问某个数是第几大的称为反查，可以利用二分查找或者Hash得到答案，复杂度取决于具体算法，一般为O(log(n))。</p>
<h3 id="lazy-tag"><a href="#lazy-tag" class="headerlink" title="lazy-tag"></a>lazy-tag</h3><p>这个标记一般用于处理线段树的区间更新。<br>线段树在进行区间更新的时候，为了提高更新的效率，所以每次更新只更新到更新区间完全覆盖线段树结点区间为止，这样就会导致被更新结点的子孙结点的区间得不到需要更新的信息，所以在被更新结点上打上一个标记，称为lazy-tag，等到下次访问这个结点的子结点时再将这个标记传递给子结点，所以也可以叫延迟标记。</p>
<h3 id="子树收缩"><a href="#子树收缩" class="headerlink" title="子树收缩"></a>子树收缩</h3><p>子树收缩是子树继承的逆过程，子树继承是为了两棵子树获得父结点的信息；而子树收缩则是在回溯的时候，如果两棵子树拥有相同数据的时候在将数据传递给父结点，子树的数据清空，这样下次在访问的时候就可以减少访问的结点数。</p>
<h2 id="线段树的多维推广"><a href="#线段树的多维推广" class="headerlink" title="线段树的多维推广"></a>线段树的多维推广</h2><h3 id="二维线段树-矩形树"><a href="#二维线段树-矩形树" class="headerlink" title="二维线段树 - 矩形树"></a>二维线段树 - 矩形树</h3><h4 id="基本结构"><a href="#基本结构" class="headerlink" title="基本结构"></a>基本结构</h4><p>二维线段树最主要用于平面统计问题。类似一维线段树，最经典的就是求区间最值（或区间和），推广到二维，求得就是矩形区域最值（或矩形区域和），对于矩形区域和，二维树状数组更加高效，而矩形区域最值，更加高效的方法是二维RMQ，但是二维RMQ不支持动态更新，所以二维线段树还是有用武之地的。<br>如果对一维线段树已经驾轻就熟，那么直接来看下面两段对比，就可以轻松理解二维线段树了。<br>一维线段树是一棵二叉树，树上每个结点保存一个区间和一个域，非叶子结点一定有两个儿子结点，儿子结点表示的两个区间交集为空，并集为父结点表示的区间；叶子结点的表示区间长度为1，即单位长度；域则表示了需要求的数据，每个父结点的域可以通过两个儿子结点得出。<br>二维线段树是一棵四叉树，树上每个结点保存一个矩形和一个域，非叶子结点一定有二或四 个儿子结点，儿子结点表示的四个矩形交集为空，并集为父结点表示的矩形；叶子结点表示的矩形长宽均为1，域则表示了需要求的数据，每个父结点的域可以通过四个儿子结点得出。<br>一个4x3的矩形，可以用下图的树形结构来表示，给每个单位方块标上不同的颜色易于理解。<br><img src="_v_images/20181207125435128_5407.webp =676x" alt="二维线段树"><br>上图中，每个叶子结点的单位面积为1，非叶子结点表示的矩形进行四分后，如下图所示，四个子矩形分别表示的是儿子结点表示的矩形区域。特殊的，当矩形面积为1 X H或者W X 1的时候，变成了一维的情况，这就是为什么有些结点有四个子结点，而有些结点只有两个子结点的原因了。<br><img src="_v_images/20181207125557701_20335.webp" alt="二维线段树2"></p>
<h4 id="时空复杂度"><a href="#时空复杂度" class="headerlink" title="时空复杂度"></a>时空复杂度</h4><p>首先来看空间复杂度，一个 W x H 的矩形，根结点表示的矩形是W x H，令N = max{W, H}，那么这棵二维线段树的深度D = log2(N)+1，当这棵树是一棵满四叉树的时候，结点数达到最大值，根据等比数列求和公式，最大情况的结点数为 (4^D - 1) / 3。更加直观的，当N = W = H = 2^k, 必定是一棵满四叉树，结点数为(4^D-1) / 3 = ( 4^(k+1) - 1 ) / 3 = (2^（2k+2）-1) / 3，去掉分子上的零头1，约等于(4/3)<em>N^2， 所以空间复杂度为O(N^2)。<br>再来看时间复杂度，需要分情况：<br>建树：建树时必定访问到每个结点，而且都是访问一次，所以建树的复杂度为O(N^2)；<br>单点更新：每次更新一个单位矩形的值，访问时只会访问从树的根结点到叶子结点的一条路径，所以单点更新的复杂度为O( log2(N) )。<br>区域询问：情况类似一维的区间询问。从根结点开始拆分区域，当询问区域完全覆盖结点区域时，不需要递归往下走，总体复杂度是O( log2(N) </em> log2(N) )  ？ 这里还是打个问号先，具体是一个log还是两个log记不清了，找个时间证明一下，可以肯定的是，不会退化成O(N)。</p>
<h4 id="结点结构"><a href="#结点结构" class="headerlink" title="结点结构"></a>结点结构</h4><p>接下来看看每个树结点需要保存一些什么信息， 以最值为例，除了保存最值以外，有可能需要知道这个最值在整个矩形的具体坐标，所以我们的最值信息dataInfo需要保存三个信息，posx和posy表示最值的具体位置，val保存最值，由于二维线段树的空间复杂度为O(N^2)，所以坐标信息不会很大，为了尽力节省内存，坐标值用short来存即可。最值val的话看实际情况而定，一般用int就够了。<br>treeNode则是线段树结点的结构体，其中成员由dataInfo对应的最值和son[4]表示的子结点编号组成，我们的线段树结点采用静态结点，即每个线段树结点都对应静态数组 nodes中的某个元素，便于通过编号在O(1)的时间内获取到对应树结点的指针，son[4]记录了四个子结点在nodes中的下标。仔细观察可以发现，如果对于一棵线段树，保证所有结点编号都连续的情况下，如果父结点的编号确定，那么子结点的编号也就确定了。例如，根结点编号为1，那么四个子结点编号为2、3、4、5，父结点编号为2，四个子结点的编号为6、7、8、9，根据数学归纳法，当结点编号为p，那么它的四个子结点编号为(4p-2+x)，其中x取值为[0, 3]，所以四个子结点的编号信息可以通过O(1)的时间计算出来，就不用存储在线段树结点上了，大大节省了内存开销。<br>结构定义代码如下：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> LOGN 10</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAXN (1&lt;&lt;LOGN)</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAXNODES 3*(1&lt;&lt;(2*LOGN)/4 + 100)</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> son(x) (p*4-2+x)</span></span><br><span class="line"><span class="comment">// 最值信息</span></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">dataInfo</span> &#123;</span></span><br><span class="line">    <span class="keyword">short</span> posx, posy;</span><br><span class="line">    <span class="keyword">int</span> val;</span><br><span class="line">    dataInfo() &#123;</span><br><span class="line">        posx = posy = val = <span class="number">-1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    dataInfo(<span class="keyword">short</span> _posx, <span class="keyword">short</span> _posy, <span class="keyword">int</span> _val) &#123;</span><br><span class="line">        posx = _posx;</span><br><span class="line">        posy = _posy;</span><br><span class="line">        val = _val;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line"><span class="comment">// 线段树结点信息</span></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">treeNode</span> &#123;</span></span><br><span class="line">    <span class="comment">// int son[4]</span></span><br><span class="line">    dataInfo maxv, minv;</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">reset</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        maxv = dataInfo(<span class="number">0</span>, <span class="number">0</span>, INT_MIN);</span><br><span class="line">        minv = dataInfo(<span class="number">0</span>, <span class="number">0</span>, INT_MAX);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;nodes[ MAXNODES ];</span><br><span class="line"></span><br><span class="line"><span class="comment">// 注意，这里需要返回指针，因为在后续使用中需要对这个结点的信息进行改变，如果返回对象的话只是一个copy，不会改变原结点的内容</span></span><br><span class="line"><span class="function">treeNode* <span class="title">getNode</span><span class="params">(<span class="keyword">int</span> id)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">return</span> &amp;nodes[id];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这时候，我们发现线段树的结点上还缺少一个很重要的信息，因为每个结点表示了一个矩形区域，那为什么没有存下这个矩形区域呢？毋庸置疑，也是为了节省内存，在接下来的区域查询、单点更新的介绍中会讲到，这个区域其实在每次递归的时候是作为传参进入函数内部的，结点编号确定，矩形区域就确定了，所以没必要存储在结点中。</p>
<h4 id="区间类"><a href="#区间类" class="headerlink" title="区间类"></a>区间类</h4><p>为了处理方便，我们还需要封装一个区间类（由于矩形可以表示成两个不同维度的区间，所以这里只需要封装一个区间类即可，矩形类的操作没有区间内那么简单，一目了然），它支持一些基本操作，如判交、判包含、取左右半区间等等、，具体代码如下：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Interval</span> &#123;</span></span><br><span class="line">    <span class="keyword">int</span> l, r;</span><br><span class="line">    Interval() &#123;&#125;</span><br><span class="line">    Interval(<span class="keyword">int</span> _l, <span class="keyword">int</span> _r) &#123;</span><br><span class="line">        l = _l;</span><br><span class="line">        r = _r;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 区间中点 </span></span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">mid</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> (l + r) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 区间长度 </span></span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">len</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> r - l + <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 左半区间 </span></span><br><span class="line">    <span class="function">Interval <span class="title">left</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> Interval(l, mid());</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 右半区间 </span></span><br><span class="line">    <span class="function">Interval <span class="title">right</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> Interval(mid()+<span class="number">1</span>, r);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 区间判交</span></span><br><span class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">isIntersectWith</span><span class="params">( Interval&amp; tarI )</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> !( l &gt; tarI.r || r &lt; tarI.l );</span><br><span class="line">    &#125; </span><br><span class="line">    <span class="comment">// 区间判包含</span></span><br><span class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">isInclude</span><span class="params">( Interval&amp; tarI )</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> l &lt;= tarI.l &amp;&amp; tarI.r &lt;= r;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">in</span> <span class="params">(<span class="keyword">int</span> v)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> l &lt;= v &amp;&amp; v &lt;= r;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h4 id="建树"><a href="#建树" class="headerlink" title="建树"></a>建树</h4><p>那么接下来就是建树了，建树就是递归生成结点的过程，这里的生成并非创建，原因是因为我们的结点是静态的。每建一次树，只是把所有线段树结点的信息进行一次重置，对于一个W x H的矩形，假定它的两个对角线坐标为(1, 1) - (W, H)，那么我们首先将它切割成四个矩形，令WM = (1+W)/2, HM = (1+H)/2对角线坐标分别为：<br>        (1, 1) - (WM, HM)<br>        (WM+1, 1) - (W, HM)<br>        (1, HM+1) - (WM, H)<br>        (WM+1, HM+1) - (W, H)<br>如下图所示，四个切割完后的矩形如下：<br><img src="_v_images/20181207130453688_3915.webp =658x" alt="二维线段树建树"><br>这个切割过程是递归进行的，当某次切割的矩形为单位面积的时候，即为递归出口。当然还有一种情况，就是当某次切割后的矩形的某一维为1，而另一维大于1时，这里假设W = 1，H &gt; 1，那么继续切割时会发现WM+1 &gt; W,导致 (WM+1, 1) - (W, HM) 和 (WM+1, HM+1) - (W, H) 这两个矩形面积为负，所以在递归入口处需要判断是否有某一维的右端点小于左端点，如果有，这种矩形是不合法的，不能做为线段树的结点，不需要继续往下递归创建。<br>建树代码如下：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">build_segtree</span><span class="params">(<span class="keyword">int</span> p, Interval xI, Interval yI)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// 空矩形（右端点小于左端点）</span></span><br><span class="line">    <span class="keyword">if</span>(xI.len() &lt;= <span class="number">0</span> || yI.len() &lt;= <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    &#125;</span><br><span class="line">    treeNode* now = getNode(p);</span><br><span class="line">    <span class="comment">// 结点初始化</span></span><br><span class="line">    now-&gt;reset();</span><br><span class="line">    <span class="comment">// 单位矩形</span></span><br><span class="line">    <span class="keyword">if</span>(xI.len() == <span class="number">1</span> &amp;&amp; yI.len() == <span class="number">1</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    &#125;</span><br><span class="line">    build_segtree( son(<span class="number">0</span>), xI.left(), yI.left() );</span><br><span class="line">    build_segtree( son(<span class="number">1</span>), xI.right(), yI.left());</span><br><span class="line">    build_segtree( son(<span class="number">2</span>), xI.left(), yI.right() );</span><br><span class="line">    build_segtree( son(<span class="number">3</span>), xI.right(), yI.right());   </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>其中p为当前线段树结点的编号，son(0) ~ son(3)则是作为子结点编号传参进入切割后的矩形, getNode(p)用于获取编号为p的结点的结构指针，建树的目的就是为每个结点进行初始化，如果求的是最大值，那么将结点上的域都设成 INT_MIN ( 只要比所有接下来要插入的值小即可 )，如果求的是最小值，那么结点上的域都设成 INT_MAX( 只要比所有接下来要插入的值大即可 )。<br>建树完毕后，这些结点都有了一个初始值，那么接下来就是需要在矩形的每个点插入一个值，然后更新线段树上每个结点的最值信息了。</p>
<h4 id="插入"><a href="#插入" class="headerlink" title="插入"></a>插入</h4><p>插入过程和建树过程的思想是一致的，同样是将矩形切割成四份，因为插入的是一个点，所以不可能同时存在于任意两个矩形中（因为是个矩形是互不相交的），所以每次四分只会选择一个矩形进行插入，为了让代码简洁，我们还是先将矩形进行切割，然后模拟所有的矩形都能够插入，然后在递归入口处判断该点是否在矩形区域中，如果不在矩形区域直接返回。这样，当递归到单位矩形的时候，这个点的坐标一定是和矩形的坐标重合的，就可以直接更新该矩形所在的线段树结点的域信息了，更新完这个单位矩形还不够，还需要将信息传递给它的父结点，因为每次更新只有一个点，所以改变的结点只有从这个单位矩形所在结点到根结点的一条路径上的结点，所以复杂度是树的深度，即O(log2(N))。<br>插入结点（单点更新）代码如下：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">insert_segtree</span><span class="params">(<span class="keyword">int</span> p, Interval xI, Interval yI, <span class="keyword">int</span> x, <span class="keyword">int</span> y, <span class="keyword">int</span> val)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(xI.len() &lt;= <span class="number">0</span> || yI.len() &lt;= <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>( !xI.in(x) || !yI.in(y) ) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    treeNode *now = getNode(p);</span><br><span class="line">    <span class="keyword">if</span>(xI.len() == <span class="number">1</span> &amp;&amp; yI.len() == <span class="number">1</span>) &#123;</span><br><span class="line">        now-&gt;maxv = now-&gt;minv = dataInfo(x, y, val);</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">bool</span> isvalid[<span class="number">4</span>];</span><br><span class="line">    isvalid[<span class="number">0</span>] = insert_segtree( son(<span class="number">0</span>), xI.left(), yI.left(), x, y, val );</span><br><span class="line">    isvalid[<span class="number">1</span>] = insert_segtree( son(<span class="number">1</span>), xI.right(), yI.left(), x, y, val );</span><br><span class="line">    isvalid[<span class="number">2</span>] = insert_segtree( son(<span class="number">2</span>), xI.left(), yI.right(), x, y, val );</span><br><span class="line">    isvalid[<span class="number">3</span>] = insert_segtree( son(<span class="number">3</span>), xI.right(), yI.right(), x, y, val ); </span><br><span class="line">   </span><br><span class="line">    <span class="comment">// 通过四个子结点的信息更新父结点 </span></span><br><span class="line">    now-&gt;maxv = dataInfo(<span class="number">0</span>, <span class="number">0</span>, MIN_VAL);</span><br><span class="line">    now-&gt;minv = dataInfo(<span class="number">0</span>, <span class="number">0</span>, MAX_VAL);</span><br><span class="line">    <span class="keyword">int</span> i;</span><br><span class="line">    <span class="keyword">for</span>(i = <span class="number">0</span>;i &lt; <span class="number">4</span>; i++) &#123;</span><br><span class="line">        <span class="keyword">if</span>( !isvalid[i] ) <span class="keyword">continue</span>;</span><br><span class="line">        treeNode *sonNode = getNode(son(i));</span><br><span class="line">        now-&gt;maxv = sonNode-&gt;maxv.val &gt; now-&gt;maxv.val ? sonNode-&gt;maxv : now-&gt;maxv;</span><br><span class="line">        now-&gt;minv = sonNode-&gt;minv.val &lt; now-&gt;minv.val ? sonNode-&gt;minv : now-&gt;minv;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span>; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>可以发现，插入的核心代码和建树是一致的，但是这里的插入操作，返回了一个值，表示的是当前插入的线段树结点p是否合法，因为我们在插入的时候无论如何都会将矩形切割成四份，没有去考虑上文中提到的有一维为1的情况，父结点的域值是通过子结点回溯上来进行更新的，如果子结点不合法，不应该作为更新的依据，所以作为父结点，需要知道哪些结点是不合法的。</p>
<h4 id="询问-1"><a href="#询问-1" class="headerlink" title="询问"></a>询问</h4><p>有了更新，当然需要询问，没有询问，更新也就失去了意义。<br>询问一般是区域询问（单点询问就没必要用线段树了）。<br><img src="_v_images/20181207131222478_448.webp" alt="矩形树询问"><br>如上图所示，在一个4 x 3的矩形中，需要询问灰色的矩形（3 x 2的矩形，以下统一称为询问矩形）中最大的数是什么。首先来说说原理，同样，和建树以及插入操作一样，我们首先不断将矩形进行切割，每当访问到一个结点的时候将询问矩形和结点矩形进行判交测试，一共有以下几种情况：<br>       1、询问矩形 和 结点矩形 <strong>没有交集</strong> （图中所有白色的叶子结点）；<br>       2、询问矩形 <strong>完全包含 </strong>结点矩形 （图中根结点的第三个子结点）；<br>       3、询问矩形 <strong>不完全包含</strong> 结点矩形，并且存在交集（图中根结点的第一、二、四个子结点）；<br>首先我们需要保存一个全局最大值信息，这个信息可以通过引用的方式传递到函数中去，在递归的过程中不断迭代更新；<br>对于第1、2两种情况都是不需要继续往下递归的，第1种情况不会影响目前的最大值，第2种情况需要将结点上的最大值和全局最大值进行比较，保留大的那个；第三种情况有交集，所以我们需要将矩形继续分割，直到出现第1或者第2种情况为止，而且一定是可以出现的。<br>区域询问代码如下：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// query_type 0 最大值   1最小值</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">query_segtree</span><span class="params">(<span class="keyword">int</span> p, Interval xI, Interval yI, Interval tarXI, Interval tarYI, dataInfo&amp; ans, <span class="keyword">int</span> query_type)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(xI.len() &lt;= <span class="number">0</span> || yI.len() &lt;= <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    &#125;</span><br><span class="line">   </span><br><span class="line">    <span class="keyword">if</span>( !tarXI.isIntersectWith(xI) || !tarYI.isIntersectWith(yI) ) &#123;</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    &#125;</span><br><span class="line">    treeNode *now = getNode(p);</span><br><span class="line">   </span><br><span class="line">    <span class="comment">// 最大值优化 </span></span><br><span class="line">    <span class="keyword">if</span>(query_type == <span class="number">0</span> &amp;&amp; ans.val &gt;= now-&gt;maxv.val) &#123;</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 最小值优化 </span></span><br><span class="line">    <span class="keyword">if</span>(query_type == <span class="number">1</span> &amp;&amp; ans.val &lt;= now-&gt;minv.val) &#123;</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    &#125;</span><br><span class="line">       </span><br><span class="line">    <span class="keyword">if</span>(tarXI.isInclude(xI) &amp;&amp; tarYI.isInclude(yI)) &#123;</span><br><span class="line">        <span class="keyword">if</span>(query_type == <span class="number">0</span>) &#123;</span><br><span class="line">            ans = now-&gt;maxv;</span><br><span class="line">        &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">            ans = now-&gt;minv;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    &#125;</span><br><span class="line">    query_segtree( son(<span class="number">0</span>), xI.left(), yI.left(), tarXI, tarYI, ans, query_type );</span><br><span class="line">    query_segtree( son(<span class="number">1</span>), xI.right(), yI.left(), tarXI, tarYI, ans, query_type );</span><br><span class="line">    query_segtree( son(<span class="number">2</span>), xI.left(), yI.right(), tarXI, tarYI, ans, query_type );</span><br><span class="line">    query_segtree( son(<span class="number">3</span>), xI.right(), yI.right(), tarXI, tarYI, ans, query_type ); </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这里加入了一个query_type，表示求的是最大值还是最小值，因为有的时候既需要知道最大值，又需要知道最小值，为了简化函数个数引入的一个变量。这里我们发现，<strong>当求最大值的时候，如果 询问矩形 和 结点矩形 是有交集并且并非完全包含的情况下，如果结点最大值比全局最大值（以上代码中的ans即全局最大值信息）还小，那么没必要再往下递归了，因为递归下去的最大值不会比当前结点的最大值大</strong>，这个优化很重要。<br>以上就是二维线段树通过三个函数实现求区域最值的全部内容，建树(build_segtree)、插入(insert_segtree) 、询问(query_segtree),其实当我们将这三个函数中的 yI 这个区间变成[1, 1]的时候，就变成了一维线段树的模板了。</p>
<h3 id="三维线段树-空间树"><a href="#三维线段树-空间树" class="headerlink" title="三维线段树 - 空间树"></a>三维线段树 - 空间树</h3><p>线段树-二叉树，二维线段树-四叉树，三维线段树自然就是八叉树了，分割的是空间，一般用于三维计算几何，当然也不一定用在实质的空间内的问题。</p>
<h2 id="线段树相关题集整理"><a href="#线段树相关题集整理" class="headerlink" title="线段树相关题集整理"></a>线段树相关题集整理</h2><p><a href="http://www.cppblog.com/menjitianya/category/16397.html" target="_blank" rel="noopener">线段树题集题解</a></p>
<h2 id="参考博文链接"><a href="#参考博文链接" class="headerlink" title="参考博文链接"></a>参考博文链接</h2><p><a href="https://blog.csdn.net/whereisherofrom/article/details/78969718" target="_blank" rel="noopener">夜深人静写算法（七）- 线段树</a><br><a href="http://www.cppblog.com/menjitianya/archive/2015/10/06/211956.html" target="_blank" rel="noopener">二维线段树</a><br><a href="https://blog.csdn.net/abc13068938939/article/details/52038004" target="_blank" rel="noopener">线段树进阶学习</a></p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2018/12/08/线段树/" data-id="cjpevtebt00029gtkxpkbaagx" class="article-share-link">Share</a>
      
      
    </footer>
  </div>
  
    
<nav id="article-nav">
  
  
    <a href="/2018/12/08/树状数组/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title"></div>
    </a>
  
</nav>

  
</article>

</section>
        
          <aside id="sidebar">
  
    

  
    

  
    
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/12/">December 2018</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2018/12/08/线段树/">线段树</a>
          </li>
        
          <li>
            <a href="/2018/12/08/树状数组/">(no title)</a>
          </li>
        
          <li>
            <a href="/2018/12/08/hello/">hello</a>
          </li>
        
          <li>
            <a href="/2018/12/07/hello-world/">Hello World</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2018 John Doe<br>
      Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>
    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    

<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>


  <link rel="stylesheet" href="/fancybox/jquery.fancybox.css">
  <script src="/fancybox/jquery.fancybox.pack.js"></script>


<script src="/js/script.js"></script>



  </div>
</body>
</html>